package leetcode.graph.maxFlow.lcp04;

import graph.matchProblem.CandyBipartiteMatching;
import graph.unweighted.CandyGraph;

/**
 * 
 * @Title: Solution.java 
 * @Package leetcode.graph.maxFlow.lcp04 
 * @Description: LCP 04. 覆盖
 * @author CandyWall   
 * @date 2021年1月23日 下午2:10:04 
 * @version V1.0
 */
public class Solution {
    public int domino(int n, int m, int[][] broken) {
        int[][] board = new int[n][m];
        for(int[] p : broken) {
            board[p[0]][p[1]] = 1;
        }
        CandyGraph graph = new CandyGraph(n * m, false);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j] == 0) {
                    // 看下左边和下边的各自是否完好，若是完好的，建图的时候就连上一条边
                    if(j + 1 < m && board[i][j + 1] == 0) {
                        graph.addEdge(i * m + j, i * m + j + 1);
                    }
                    if(i + 1 < n && board[i + 1][j] == 0) {
                        graph.addEdge(i * m + j, (i + 1) * m + j);
                    }
                }
            }
        }
        
        CandyBipartiteMatching matching = new CandyBipartiteMatching(graph);
        
        return matching.getMaxMatching();
    }
    
    public static void main(String[] args) {
        int n = 2, m = 3;
        int[][] broken = {{1, 0}, {1, 1}};
        System.out.println(new Solution().domino(n, m, broken));
        n = 3;
        m = 3;
        int[][] broken1 = {};
        System.out.println(new Solution().domino(n, m, broken1));
    }
}
